/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */
public class BinaryTreeFromInorderAndPreorder {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		int len = preorder.length;
		if (len == 0)
			return null;
		TreeNode root = new TreeNode(preorder[0]);
		int i = 0;
		for (; i < len; ++i)
			if (inorder[i] == root.val)
				break;
		int lpr[] = new int[i];
		int lin[] = new int[i];
		for (int j = 0; j < i; ++j) {
			lpr[j] = preorder[j + 1];
			lin[j] = inorder[j];
		}
		root.left = buildTree(lpr, lin);

		int rpr[] = new int[len - 1 - i];
		int rin[] = new int[len - 1 - i];
		for (int j = 0; j < len - 1 - i; ++j) {
			rpr[j] = preorder[i + j + 1];
			rin[j] = inorder[i + j + 1];
		}
		root.right = buildTree(rpr, rin);

		return root;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
